package 简单.双指针;

/**
 * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
 * <p>
 * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
 * <p>
 * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
 * <p>
 * 返回还剩多少个元素
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-element
 */
public class 移除元素_27 {

    public static void main(String[] args) {

        int[] nums = {0, 1, 2, 2, 3, 0, 4, 2};
        System.out.println(efficientRemoveElement(nums, 2));

    }

    /**
     * 遇到=val的元素，后面元素往前移一位
     *
     * @param nums
     * @param val
     * @return
     */
    public static int removeElement(int[] nums, int val) {
        int count = nums.length;
        for (int i = 0; i < count; ) {
            int j = i;
            if (nums[j] == val) {
                --count;
                while (j < count) {
                    nums[j] = nums[j + 1];
                    ++j;
                }
            } else {
                i++;
            }
        }
        return count;
    }

    /**
     * left1代表左边都不等于val的右边界
     * left2来判断是否等于val
     * left2永远在left1的前面
     *
     * @param nums
     * @param val
     * @return
     */
    public static int removeElement2(int[] nums, int val) {
        int left1 = 0;
        for (int left2 = 0; left2 < nums.length; left2++) {
            if (nums[left2] != val) {
                nums[left1] = nums[left2];
                left1++;
            }
        }
        return left1;
    }

    /**
     * 双指针优化
     * 优化问题：
     * 如果是之前的双指针，原理是将所有不等于val的元素往前移，而题目说可以改变顺序
     * 所以：
     * 可以将左指针不等于val的元素和右指针等于val的元素进行交换，交换过来的元素任然
     * 需要判断，只有确定了左指针的值不等于val时，才往右移
     * <p>
     * 如果先判断后右边的值不等于val才交换位置的话，
     * 那么左指针是否左移不会判断
     *
     * @param nums
     * @param val
     * @return
     */
    public static int efficientRemoveElement(int[] nums, int val) {

        int left = 0, right = nums.length - 1;
        while (left <= right) {
            if (nums[left] == val) {
                nums[left] = nums[right];
                right--;
            } else { //左指针等于val才往右移
                left++;
            }
        }
        return left;
    }


}
